The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(q0(0(x1))) → 0(0(q0(x1)))
0(q0(h(x1))) → 0(0(q0(h(x1))))
0(q0(1(x1))) → 0(1(q0(x1)))
1(q0(0(x1))) → 0(0(q1(x1)))
1(q0(h(x1))) → 0(0(q1(h(x1))))
1(q0(1(x1))) → 0(1(q1(x1)))
1(q1(0(x1))) → 1(0(q1(x1)))
1(q1(h(x1))) → 1(0(q1(h(x1))))
1(q1(1(x1))) → 1(1(q1(x1)))
0(q1(0(x1))) → 0(0(q2(x1)))
0(q1(h(x1))) → 0(0(q2(h(x1))))
0(q1(1(x1))) → 0(1(q2(x1)))
1(q2(0(x1))) → 1(0(q2(x1)))
1(q2(h(x1))) → 1(0(q2(h(x1))))
1(q2(1(x1))) → 1(1(q2(x1)))
0(q2(x1)) → q3(1(x1))
1(q3(x1)) → q3(1(x1))
0(q3(x1)) → q4(0(x1))
1(q4(x1)) → q4(1(x1))
0(q4(0(x1))) → 1(0(q5(x1)))
0(q4(h(x1))) → 1(0(q5(h(x1))))
0(q4(1(x1))) → 1(1(q5(x1)))
1(q5(0(x1))) → 0(0(q1(x1)))
1(q5(h(x1))) → 0(0(q1(h(x1))))
1(q5(1(x1))) → 0(1(q1(x1)))
h(q0(x1)) → h(0(q0(x1)))
h(q1(x1)) → h(0(q1(x1)))
h(q2(x1)) → h(0(q2(x1)))
h(q3(x1)) → h(0(q3(x1)))
h(q4(x1)) → h(0(q4(x1)))
h(q5(x1)) → h(0(q5(x1)))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4.
The certificate found is represented by the following graph.

Start state: 3913
Accept states: [3914, 3916, 3917]
Transitions:
3913→3914[0_1|0]
3913→3916[1_1|0]
3913→3917[h_1|0]
3913→3913[q0_1|0, q1_1|0, q2_1|0, q3_1|0, q4_1|0, q5_1|0]
3913→3919[1_1|1]
3913→3920[q2_1|1]
3913→3922[0_1|1]
3913→3923[1_1|1]
3913→3924[q3_1|1]
3913→3926[1_1|1]
3913→3927[q4_1|1]
3913→3929[q0_1|1]
3913→3931[q1_1|1]
3913→3933[q5_1|1]
3913→3935[1_1|2]
3913→3936[0_1|2]
3913→3944[q5_1|3]
3913→3949[q5_1|2]
3919→3914[q3_1|1]
3919→3922[q3_1|1]
3919→3936[q3_1|1]
3920→3921[0_1|1]
3921→3917[h_1|1]
3922→3914[q4_1|1]
3922→3922[q4_1|1]
3922→3936[q4_1|1]
3923→3916[q3_1|1]
3923→3919[q3_1|1]
3923→3923[q3_1|1]
3923→3926[q3_1|1]
3923→3935[q3_1|1]
3923→3951[0_1|2]
3924→3925[0_1|1]
3925→3917[h_1|1]
3926→3916[q4_1|1]
3926→3919[q4_1|1]
3926→3923[q4_1|1]
3926→3926[q4_1|1]
3926→3935[q4_1|1]
3927→3928[0_1|1]
3928→3917[h_1|1]
3929→3930[0_1|1]
3930→3917[h_1|1]
3931→3932[0_1|1]
3932→3917[h_1|1]
3933→3934[0_1|1]
3934→3917[h_1|1]
3935→3921[q3_1|2]
3935→3940[q3_1|2]
3935→3946[0_1|3]
3935→3954[q5_1|4]
3936→3925[q4_1|2]
3936→3942[q4_1|2]
3940→3941[0_1|2]
3941→3917[h_1|2]
3942→3943[0_1|2]
3943→3917[h_1|2]
3944→3945[0_1|3]
3945→3943[1_1|3]
3946→3941[q4_1|3]
3946→3952[q4_1|3]
3949→3950[1_1|2]
3949→3958[q1_1|3]
3950→3946[1_1|2]
3950→3951[1_1|2]
3950→3956[q5_1|3]
3951→3946[q4_1|2]
3951→3951[q4_1|2]
3952→3953[0_1|3]
3953→3917[h_1|3]
3954→3955[0_1|4]
3955→3953[1_1|4]
3956→3957[1_1|3]
3957→3953[1_1|3]
3958→3959[1_1|3]
3959→3957[0_1|3]

(2) BOUNDS(O(1), O(n^1))